package leetcode;

import javax.xml.crypto.dsig.keyinfo.KeyValue;
import java.util.HashMap;
import java.util.SortedMap;
import java.util.TreeMap;

/*
在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。

给你一个整数数组 arr，请你从中找出并返回一个幸运数。

如果数组中存在多个幸运数，只需返回 最大 的那个。
如果数组中不含幸运数，则返回 -1 。
 

示例 1：

输入：arr = [2,2,3,4]
输出：2
解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。
 */
public class Test1394 {
    public int findLucky(int[] arr) {
//        int[] bucket=new int[501];
//        HashMap<Integer,Integer> dic= new HashMap<Integer, Integer>();
//        int res=Integer.MIN_VALUE;
//        for(int i=0;i<arr.length;i++){
//            if(dic.containsKey(arr[i]))
//                dic.remove(arr[i]);
//            bucket[arr[i]]++;
//            if(bucket[arr[i]]==arr[i]){
//                dic.put(arr[i],0);
//            }
//        }
//        for(int key:dic.keySet()){
//            if(key>res){
//                res= key;
//            }
//        }
//        return res;
        int[] bucket=new int[501];
        int res=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            bucket[arr[i]]++;
        }
        for(int i=bucket.length-1;i>=1;i--){
            if(bucket[i]==i)
                return i;
        }
        return -1;
    }
}
